package tree.traverse;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/
 *
 * 后序遍历
 */
public class PostOrder {
    public static void main(String[] args) {
        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);

        PostOrder bt = new PostOrder();
        // 2 4 5 3 1
        System.out.println("后序遍历： " + bt.postOrder(treeNode));
    }
    /**
     * 后序遍历（根后，从左到右）  将树各个节点拆分
     * @param root 树
     * @return 结果
     */
    public List<Integer> postOrder(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();
        if(root == null)
        {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty())
        {
            TreeNode node = stack.peek();

            if(node.left == null && node.right == null)
            {
                TreeNode tmpNode = stack.pop();
                result.add(tmpNode.val);
            }

            if(node.right !=null)
            {
                stack.push(node.right);
                node.right=null;
            }

            if(node.left !=null)
            {
                stack.push(node.left);
                node.left = null;
            }

        }
        return result;
    }
}
